package com.zhugang.week13.slidingwindow;

import java.util.HashSet;
import java.util.Set;

/**
 * @program algorithms
 * @description: lengthOfLongestSubstring
 * @author: chanzhugang
 * @create: 2022/09/19 16:17
 */
public class LengthOfLongestSubstring {

    /**
     * 剑指offer 48 最长不含重复字符的子字符串
     * https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        // 连续最长不重复子串： 想到滑动窗口
        int i = 0;
        int j = 0;
        Set<Character> set = new HashSet<>();
        int maxLength = Integer.MIN_VALUE;
        while (j < s.length()) {
            char c = s.charAt(j);
            if (!set.contains(c)) {
                set.add(c);
                j++;
                maxLength = Math.max(maxLength, j - i);
                continue;
            }

            // 包含了重复元素
            while (set.contains(c)) {
                // 把重复元素之前的都删掉
                set.remove(s.charAt(i));
                i++;
            }
        }
        return maxLength;
    }

    // 代码更简洁，优雅
    public int lengthOfLongestSubstring2(String s) {
        // 滑动窗口
        Set<Character> set = new HashSet<>();
        int maxLen = 0;
        for (int l = 0, r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            // 重复需要一直删除
            while (set.contains(c)) {
                set.remove(s.charAt(l++));
            }
            set.add(c);
            maxLen = Math.max(maxLen, r - l + 1);
        }
        return maxLen;
    }


}